package mazeAssignment.datastructures;

import java.util.ArrayList;
import java.util.List;

public class DisjointSet
{
	private DisjointSet mParent = null;
	
	
	public static DisjointSet union(DisjointSet pFirstSet, DisjointSet pSecondSet)
	{
		pSecondSet.setTopLevelParent( pFirstSet.getTopLevelParent() );
		return pFirstSet;
	}
	
	public static boolean isSameSet(DisjointSet pFirstSet, DisjointSet pSecondSet)
	{
		return pFirstSet.getTopLevelParent() == pSecondSet.getTopLevelParent();
	}
	
	public DisjointSet getTopLevelParent()
	{
		List<DisjointSet> obsoleteParents = new ArrayList<DisjointSet>();
		DisjointSet lCurrent = this;
		while(lCurrent.mParent != null)
		{
			obsoleteParents.add(lCurrent);
			lCurrent = lCurrent.mParent;
		}
		
		//Update obsolete parents
		for(DisjointSet ds : obsoleteParents) {
			ds.mParent = lCurrent;
		}
		return lCurrent;
	}
	
	private void setTopLevelParent(DisjointSet pNewParent)
	{
		DisjointSet lCurrent = this;
		
		while(lCurrent.mParent != null)
		{
			DisjointSet previous = this;
			lCurrent = lCurrent.mParent;
			previous.mParent = pNewParent;
		}
		lCurrent.mParent = pNewParent;
	}
}
